package com.mypaper.schedule;

import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.PairElement;
import com.mypaper.elem.ScheduleElement;
import com.mypaper.elem.ScheduleNode;
import com.mypaper.elem.TaskAttribute;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.IdleList;
import com.mypaper.list.ListPriority;
import com.mypaper.list.ScheduleResults;



public class OptimizeSchedule_back {
	/*
	 *Input: Schedule
	 *Output: Schedule after deleting abundant copies
	 */
	private ScheduleResults[] origResultsPerProc;
	private ScheduleResults[] scheResultsPerProc;//last schedule 
	private ScheduleResults[] allProcPerTask;
	private ScheduleElement[] procFixedCopy;
	private ListPriority priorBLevel;
	private ListPriority prior;//按优先级的逆序
	private IdleList[] idleLists;
	
	
	public OptimizeSchedule_back(ListPriority prior, ListPriority priorBLevel, ScheduleAlgorithm scheAlgo, int procNum, int taskNum){
		scheResultsPerProc=new ScheduleResults[procNum];//the result schedule
		origResultsPerProc=new ScheduleResults[procNum];//the original schedule
		ScheduleResults origResults=scheAlgo.scheduleResults;
		for(int i=0;i<procNum;i++){
			origResultsPerProc[i]=new ScheduleResults();
			scheResultsPerProc[i]=new ScheduleResults();
		}
		
		procFixedCopy=new ScheduleElement[taskNum];//记录fixed copy所在的处理器
		allProcPerTask=new ScheduleResults[taskNum];//record all processors having copies of each task
		for(int i=0;i<taskNum;i++){
			procFixedCopy[i]=new ScheduleElement();
			allProcPerTask[i]=new ScheduleResults();
		}
		
		ScheduleNode sNode=origResults.first;
		while(sNode!=null){
			origResultsPerProc[sNode.info.processorID].insertNode(sNode.info);//将调度结果分解到各个处理器单独的调度结果，方便以后查找
			sNode=sNode.next;
		}
		//get the original schedule produced by duplication-based algorithms
		this.priorBLevel=priorBLevel;
		this.prior=prior;//get priority
		this.idleLists=new IdleList[procNum];
		for(int i=0;i<procNum;i++){
			idleLists[i]=scheAlgo.idleTimeList[i];//get idle time list for each processor
			//System.out.print("idleLists["+i+"]:");
			//LinkedListNode curr=idleLists[i].first;
			/*while(curr!=null){
				System.out.print(curr.info);
				curr=curr.next;
			}
			System.out.println();*/
		}
		
	}
	
	public void Optimize_Schedule(int taskNum, int procNum, float[][] vertexWeight, float[][] edgeWeight, float makespan){
		phaseST(taskNum, procNum, vertexWeight, edgeWeight, makespan);	
		System.out.println("Phase 1");
		printSchedule(procNum,taskNum);
		phaseND(taskNum, procNum, vertexWeight, edgeWeight);
		System.out.println("Phase 2");
		printSchedule(procNum,taskNum);
		phaseRD(taskNum, procNum, vertexWeight, edgeWeight, makespan);
		System.out.println("Phase 3");
		printSchedule(procNum,taskNum);
		phaseTH(taskNum, procNum, vertexWeight, edgeWeight);
		System.out.println("Phase 4");
		printSchedule(procNum,taskNum);
	}
	
	
	
	public void updateAllProcPerTask(int taskNum, int procNum){
		//搜索一次schedule，为currTask找fixed copy and all processors
		for(int i=0; i<taskNum; i++){
			allProcPerTask[i]=new ScheduleResults();
		}
		ScheduleNode currNode=new ScheduleNode();		
		for(int i=0;i<procNum;i++){	
			currNode=origResultsPerProc[i].first;
			while(currNode!=null){
				allProcPerTask[currNode.info.taskID].insertNode(currNode.info);//插入调度的结点，并判断FT
				currNode=currNode.next;
			}
		}
			
	}
	
	public void phaseST(int taskNum, int procNum, float[][] vertexWeight, float[][] edgeWeight, float makespan){
		//the first phase;
		updateFixedCopy(taskNum, procNum);
		deleteAdan(procNum, taskNum);
		updateAllProcPerTask(taskNum, procNum);
		
		/*for(int i=0; i<taskNum; i++){
			System.out.println("Task "+i+":"+procFixedCopy[i]);
			
		}*/
		//计算所有任务的lft
		boolean[] isNoChild=new boolean[taskNum];
		for(int i=0; i<taskNum; i++){//判断任务是否有孩子
			isNoChild[i]=true;
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[i][j]>0)
					isNoChild[i]=false;
			}
		}
		float[][] lft=new float[taskNum][procNum];
		
		//初始化lft;
		for(int i=0; i<taskNum; i++)
			for(int j=0; j<procNum; j++)
				if(isNoChild[i]==true)
					lft[i][j]=makespan;
				else
					lft[i][j]=Float.MAX_VALUE;		
		
		float alft;
		TaskNode currNode=new TaskNode();
		currNode=prior.first;
		while(currNode!=null){
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			ScheduleNode tempNode=allProcPerTask[taskSN].first;//获得当前任务的第一个处理器情况结点
			while(tempNode!=null){
				ScheduleElement tempElement=(ScheduleElement)tempNode.info;
				int procSN=tempElement.processorID;
				//计算每个处理器上每个任务的lft(),须知每个任务在每个处理器上的
				//local parents, the fixed copy of non_local parents
				
				lft[taskSN][procSN]=calcLFT(taskSN, procSN, taskNum, procNum, procFixedCopy, edgeWeight, lft);//calculate lft of task 
				
				if(Math.round(lft[taskSN][procSN])!=Math.round(tempElement.endTime)){//lft is different from the finish time
					ScheduleElement changeNode=tempElement.getCopy();
					
					alft=calcAFT(taskSN, procSN, tempElement.endTime, lft[taskSN][procSN], (IdleList)idleLists[procSN], vertexWeight);//计算实际可移至的时间并移动任务；
					allProcPerTask[taskSN].updateNode(changeNode, alft-vertexWeight[taskSN][procSN], alft);//update 
					origResultsPerProc[procSN].updateNode(changeNode, alft-vertexWeight[taskSN][procSN], alft);
				}
				//找当前任务在当前处理器上可shift的最晚位置，找空闲块
				//在找到的空闲块处执行任务，更新空闲队列spendIdle(tempElement.startTime,tempElement.endTime)
				tempNode=tempNode.next;
			}
			currNode=currNode.next;
		}
		
		deleteAdan(procNum, taskNum);//delete redundant copy whose start time = end time;
	}
	
	public void phaseRD(int taskNum, int procNum, float[][] vertexWeight, float[][] edgeWeight, float makespan){
		updateFixedCopy(taskNum, procNum);
		deleteAdan(procNum, taskNum);
		boolean flagMove=false;
		
		boolean[] isNoChild=new boolean[taskNum];
		for(int i=0; i<taskNum; i++){//判断任务是否有孩子
			isNoChild[i]=true;
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[i][j]>0)
					isNoChild[i]=false;
			}
		}	
		boolean[] isNoParent=new boolean[taskNum];
		for(int i=0; i<taskNum; i++){//判断任务是否有孩子
			isNoParent[i]=true;
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[j][i]>0)
					isNoParent[i]=false;
			}
		}
		float[][] lft=new float[taskNum][procNum];
				
		//初始化lft;
		for(int i=0; i<taskNum; i++)
			for(int j=0; j<procNum; j++)
				if(isNoChild[i]==true)
					lft[i][j]=makespan;
				else
					lft[i][j]=Float.MAX_VALUE;			
	
		float[][] est=new float[taskNum][procNum];	
		
		TaskNode currNode=new TaskNode();
		currNode=prior.first;
		while(currNode!=null){
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			if(this.allProcPerTask[taskSN].count>1){		
				ScheduleNode mergeFromNode=allProcPerTask[taskSN].first;
				int mergeFromProc=mergeFromNode.info.processorID;//记录源处理器
				while(mergeFromNode!=null){//当任务的处理器未遍历完，待改进
					mergeFromProc=mergeFromNode.info.processorID;
					if(origResultsPerProc[mergeFromProc].findTask(taskSN)==null){
						mergeFromNode=mergeFromNode.next;
						break;
					}
					ScheduleNode mergeToNode=allProcPerTask[taskSN].first;	
					while(mergeToNode!=null){
						if(origResultsPerProc[mergeFromProc].findTask(taskSN)==null){
							mergeFromNode=mergeFromNode.next;
							break;
						}
						int mergeToProc=mergeToNode.info.processorID;//记录目标处理器	
						if(origResultsPerProc[mergeToProc].findTask(taskSN)==null){
							mergeToNode=mergeToNode.next;
							break;
						}
						if(mergeToProc==mergeFromProc){
							mergeToNode=mergeToNode.next;
							if(mergeToNode==null){
								break;
							}
							mergeToProc=mergeToNode.info.processorID;//记录目标处理器
						}
					
						
						ScheduleResults copyResultOfFromProc=new ScheduleResults();
						ScheduleResults copyResultOfToProc=new ScheduleResults();
						copyResultOfFromProc.copyList(origResultsPerProc[mergeFromProc]);
						copyResultOfToProc.copyList(origResultsPerProc[mergeToProc]);
						
						IdleList copyListOfFromProc=new IdleList();
						IdleList copyListOfToProc=new IdleList();
						copyListOfFromProc.copyList(idleLists[mergeFromProc]);
						copyListOfToProc.copyList(idleLists[mergeToProc]);
						
						boolean flagDeleteDupl=true;
						origResultsPerProc[mergeFromProc].deleteNode(taskSN);//删除某处理器上的某任务
						allProcPerTask[taskSN].deleteNode(mergeFromNode.info);
						updateFixedCopy(taskNum, procNum);
						//能否提供其他处理器的数据,若不能,则目标处理器转向下一个
						int i=0;
						while(i<procNum){
							if(i==mergeFromProc){
								i++;
								continue;
							}
							ScheduleNode otherProcChild=new ScheduleNode();
							otherProcChild=origResultsPerProc[i].first;
							ScheduleElement localParent=origResultsPerProc[i].findTask(taskSN);
							while(otherProcChild!=null){
								if(edgeWeight[taskSN][otherProcChild.info.taskID]>0){
									if(localParent==null||localParent.endTime>otherProcChild.info.startTime){
										if(procFixedCopy[taskSN].endTime+edgeWeight[taskSN][otherProcChild.info.taskID]>otherProcChild.info.startTime){
											flagDeleteDupl=false;
											break;
										}
									}
								
								}
								otherProcChild=otherProcChild.next;
							}
							if(flagDeleteDupl==false){
								break;
							}
							i++;
						}
						
						if(flagDeleteDupl==false){
							origResultsPerProc[mergeFromProc].insertNode(mergeFromNode.info);//删除的某任务还原
							allProcPerTask[taskSN].insertNode(mergeFromNode.info);
						}else{
							ScheduleNode nodeIsMoved=origResultsPerProc[mergeFromProc].first;//当前处理器第一个任务
							boolean flagLocalChildExist=false;
							
							while(nodeIsMoved!=null){
								ScheduleElement nodeIsMovedInfo=nodeIsMoved.info;
								if(nodeIsMovedInfo.startTime>mergeFromNode.info.startTime){//在任务taskSN之后
									if(edgeWeight[taskSN][nodeIsMovedInfo.taskID]>0){//是taskSN的孩子结点 
										//判断是否存在本地孩子
										flagLocalChildExist=true;
									}
								}
								nodeIsMoved=nodeIsMoved.next;
							}
							
							if(flagLocalChildExist==false){//不存在本地孩子，若其他任务能提供异地孩子的数据，则删除
								if(procFixedCopy[taskSN].processorID!=mergeFromProc){
									idleLists[mergeFromProc].insertNode(new PairElement(mergeFromNode.info.startTime, mergeFromNode.info.endTime));
									break;
								}else{
									boolean isFoundEqualCopy=false;
									ScheduleElement foundCopyElement=origResultsPerProc[mergeFromProc].findTask(taskSN);
									int j=0;
									while(j<procNum){
										if(j==mergeFromProc)
											j++;
										if(j>=procNum)
								
											break;
										ScheduleElement isFixedCopy=origResultsPerProc[j].findTask(taskSN);
										if(isFixedCopy!=null&&isFixedCopy.endTime==foundCopyElement.endTime){
											isFoundEqualCopy=true;
										}
										j++;
									}
									
									if(isFoundEqualCopy==true){
										origResultsPerProc[mergeFromProc].deleteNode(mergeFromNode.info);
										allProcPerTask[taskSN].deleteNode(mergeFromNode.info);
										idleLists[mergeFromProc].insertNode(new PairElement(mergeFromNode.info.startTime, mergeFromNode.info.endTime));
									}
								}
							}
							
							nodeIsMoved=origResultsPerProc[mergeFromProc].first;
							if(flagLocalChildExist==true){					
								
								while(nodeIsMoved!=null){
									
									updateFixedCopy(taskNum, procNum);
									ScheduleElement nodeIsMovedInfo=nodeIsMoved.info;
									if(nodeIsMovedInfo.startTime>mergeFromNode.info.startTime){//在任务taskSN之后
										if(edgeWeight[taskSN][nodeIsMovedInfo.taskID]>0){//是taskSN的孩子结点 
											//判断是否父节点的其他版本能提供数据
											if(nodeIsMovedInfo.startTime>=procFixedCopy[taskSN].endTime+edgeWeight[taskSN][nodeIsMovedInfo.taskID]){//fixed copy能提供数据
												flagMove=false;//不需要移动
											}else{
												flagMove=true;
											}
											if(flagMove==true){//需要移动，看能不能移动										
												origResultsPerProc[mergeFromProc].deleteNode(nodeIsMovedInfo);//删除某处理器上的某任务
												allProcPerTask[nodeIsMovedInfo.taskID].deleteNode(nodeIsMovedInfo);
												
												updateFixedCopy(taskNum, procNum);
												est[nodeIsMovedInfo.taskID][mergeToProc]=calcESTrd(nodeIsMovedInfo.taskID, mergeToProc, taskNum, procNum, est, isNoParent, edgeWeight, vertexWeight);
												lft[nodeIsMovedInfo.taskID][mergeToProc]=calcLFTrd(nodeIsMovedInfo.taskID, mergeToProc, taskNum, procNum, procFixedCopy, edgeWeight, lft);//计算LFT及EST,判断目标处理器上是否有足够空闲时间执行
												
												float estCurr=est[nodeIsMovedInfo.taskID][mergeToProc];
												float lftCurr=Math.min(lft[nodeIsMovedInfo.taskID][mergeToProc], makespan);
												
												//System.out.print("["+estCurr+","+lftCurr+"]");
												//origResultsPerProc[mergeFromProc].insertNode(nodeIsMovedInfo);
												updateFixedCopy(taskNum, procNum);
												if(estCurr<lftCurr){//在目标处理器上找空闲空间
													if(lftCurr-estCurr>=vertexWeight[nodeIsMovedInfo.taskID][mergeToProc]){
														PairElement searchPair=idleLists[mergeToProc].searchIdleSlot(estCurr, lftCurr, vertexWeight[nodeIsMovedInfo.taskID][mergeToProc]);
														if(searchPair!=null){
															origResultsPerProc[mergeToProc].insertNode(new ScheduleElement(nodeIsMovedInfo.taskID, mergeToProc, Math.max(estCurr, searchPair.start), Math.max(estCurr, searchPair.start)+vertexWeight[nodeIsMovedInfo.taskID][mergeToProc]));
															//在某处理器上插入当前判断的子任务	
													
															allProcPerTask[nodeIsMovedInfo.taskID].insertNode(new ScheduleElement(nodeIsMovedInfo.taskID, mergeToProc, Math.max(estCurr, searchPair.start), Math.max(estCurr, searchPair.start)+vertexWeight[nodeIsMovedInfo.taskID][mergeToProc]));
															idleLists[mergeToProc].updataIdleNode(searchPair, Math.max(estCurr, searchPair.start), Math.max(estCurr, searchPair.start)+vertexWeight[nodeIsMovedInfo.taskID][mergeToProc]);
															idleLists[mergeFromProc].insertNode(new PairElement(nodeIsMovedInfo.startTime, nodeIsMovedInfo.endTime));
															//更新源处理器与目标处理器的空闲队列
															//还原复制任务在源目标处理器上的执行，为判断下一个子任务做准备
														}else{
															//以下三个else，表示若有一个子任务不满足约束条件，前面所做的移动工作全部撤销，对当前任务的判断终止
															origResultsPerProc[mergeFromProc].copyList(copyResultOfFromProc);
															origResultsPerProc[mergeToProc].copyList(copyResultOfToProc);
															idleLists[mergeFromProc].copyList(copyListOfFromProc);
															idleLists[mergeToProc].copyList(copyListOfToProc);
															updateAllProcPerTask(taskNum, procNum);
															updateFixedCopy(taskNum, procNum);
															break;
														}
													}
													else{
														origResultsPerProc[mergeFromProc].copyList(copyResultOfFromProc);
														origResultsPerProc[mergeToProc].copyList(copyResultOfToProc);
														idleLists[mergeFromProc].copyList(copyListOfFromProc);
														idleLists[mergeToProc].copyList(copyListOfToProc);
														updateAllProcPerTask(taskNum, procNum);
														updateFixedCopy(taskNum, procNum);
														break;
													}
												}
												else{								
													origResultsPerProc[mergeFromProc].copyList(copyResultOfFromProc);
													origResultsPerProc[mergeToProc].copyList(copyResultOfToProc);
													idleLists[mergeFromProc].copyList(copyListOfFromProc);
													idleLists[mergeToProc].copyList(copyListOfToProc);
													updateAllProcPerTask(taskNum, procNum);
													updateFixedCopy(taskNum, procNum);
													break;
												}
											}
										}
									}
									nodeIsMoved=nodeIsMoved.next;
								}
							}
						}
						
						
						
						//printSchedule(procNum, taskNum);
						mergeToNode=mergeToNode.next;
					}	
					if(mergeFromNode!=null){
						mergeFromNode=mergeFromNode.next;
					}
				}
			}
			currNode=currNode.next;
		}
	}
	
	public float calcLFTrd(int taskSN, int procSN, int taskNum, int procNum, ScheduleElement[] procFixedCopy, float[][] edgeWeight, float[][] lft){
		updateFixedCopy(taskNum, procNum);
		deleteAdan(procNum, taskNum);
		lft[taskSN][procSN]=Float.MAX_VALUE;
		for(int j=0; j<procNum; j++){
			ScheduleElement findMovedElem=origResultsPerProc[j].findTask(taskSN);//找到所求结点在第J个处理器上的版本
			ScheduleElement fixedCopy=procFixedCopy[taskSN];
			if(findMovedElem!=null){//在J上存在版本
				ScheduleNode firstSche=origResultsPerProc[j].first;
				ScheduleElement firstElement;
				while(firstSche!=null){
					firstElement=(ScheduleElement)firstSche.info;
					if(edgeWeight[taskSN][firstElement.taskID]>0){
						if(findMovedElem.endTime>firstElement.startTime){
							if(fixedCopy.endTime+edgeWeight[taskSN][firstElement.taskID]>firstElement.startTime){
								lft[taskSN][procSN]=Math.min(lft[taskSN][procSN], firstElement.startTime-edgeWeight[taskSN][procSN]);
							}
						}
					}
					firstSche=firstSche.next;
				}
			}else{
				ScheduleNode firstSche=origResultsPerProc[j].first;
				ScheduleElement firstElement;
				while(firstSche!=null){
					firstElement=(ScheduleElement)firstSche.info;
					if(edgeWeight[taskSN][firstElement.taskID]>0){	
						if(fixedCopy.equals(new ScheduleElement())){
							fixedCopy.endTime=Float.MAX_VALUE;
						}
						if(fixedCopy.endTime+edgeWeight[taskSN][firstElement.taskID]>firstElement.startTime){
							lft[taskSN][procSN]=Math.min(lft[taskSN][procSN], firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]);
						}		
					}
					firstSche=firstSche.next;
				}
			}		
		}
		return lft[taskSN][procSN];
	}
	
	public float calcESTrd(int taskSN, int procSN, int taskNum, int procNum, float[][] est, boolean[] isNoParent, float[][] edgeWeight, float[][] vertexWeight){		
		updateFixedCopy(taskNum, procNum);
		deleteAdan(procNum, taskNum);		
		est[taskSN][procSN]=0;
		if(isNoParent[taskSN]==true){
			est[taskSN][procSN]=0;
		}else{
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[j][taskSN]!=0){//is a parent of task
					//calculate the earliest start time of all copies of parents and shift tasks	
					ScheduleElement localCopy=origResultsPerProc[procSN].findTask(j);//父节点在本地的版本
					ScheduleElement fixedCopy=procFixedCopy[j];//FixedCopy
					if(localCopy!=null){
						est[taskSN][procSN]=Math.max(est[taskSN][procSN], Math.min(localCopy.endTime, fixedCopy.endTime+edgeWeight[j][taskSN]));
					}else{
						est[taskSN][procSN]=Math.max(est[taskSN][procSN], fixedCopy.endTime+edgeWeight[j][taskSN]);
					}
				}
			}
			//计算当前任务的EST及AST
		}
		return est[taskSN][procSN];
	}
	
	public void deleteAdan(int procNum, int taskNum){
		for(int i=0; i<procNum; i++){
			ScheduleNode current=origResultsPerProc[i].first;
			ScheduleNode trailCurrent=origResultsPerProc[i].first;
			while(current!=null){
				if(current==origResultsPerProc[i].first && current.info.startTime==current.info.endTime){//删除第一个结点
					origResultsPerProc[i].first=origResultsPerProc[i].first.next;
					if(origResultsPerProc[i].first==null)
						origResultsPerProc[i].last=null;
					origResultsPerProc[i].count--; 
				}else{
					if(current.info.startTime==current.info.endTime){	
						trailCurrent.next=current.next;	
						current=trailCurrent.next;
						origResultsPerProc[i].count--;
						if(current==null){//删除最后一个结点的情况
							origResultsPerProc[i].last=trailCurrent;
							break;
						}
					}	
				}
				trailCurrent=current;
				current=current.next;
			}	
		}
		
		for(int i=0; i<taskNum; i++){
			ScheduleNode current=allProcPerTask[i].first;
			ScheduleNode trailCurrent=allProcPerTask[i].first;
			while(current!=null){
				if(current==allProcPerTask[i].first && current.info.startTime==current.info.endTime){
					allProcPerTask[i].first=allProcPerTask[i].first.next;
					if(allProcPerTask[i].first==null){
						allProcPerTask[i].last=null;
					}
					allProcPerTask[i].count--; 
				}else{
					if(current.info.startTime==current.info.endTime){
						
						trailCurrent.next=current.next;
						current=trailCurrent.next;
						allProcPerTask[i].count--;
						if(current==null){//删除最后一个结点的情况
							allProcPerTask[i].last=trailCurrent;
							break;
						}
					}	
				}
				trailCurrent=current;
				current=current.next;
			}	
		}
	}
	
	public void updateIdleList(int procNum){
		//删除空闲队列中首尾相等的空闲
		for(int i=0; i<procNum; i++){
			LinkedListNode current=idleLists[i].first;
			PairElement currElement;
			LinkedListNode trailCurrent=idleLists[i].first;
			while(current!=null){
				currElement=(PairElement)current.info;
				if(current==idleLists[i].first && currElement.start==currElement.end){
					idleLists[i].first=idleLists[i].first.next;
					idleLists[i].count--; 
				}else{
					if(currElement.start==currElement.end){
						if(current.info.equals(idleLists[i].last.info)){
							idleLists[i].last=trailCurrent;
						}
						trailCurrent.next=current.next;
						current=trailCurrent;
						idleLists[i].count--;
					}	
				}
				trailCurrent=current;
				current=current.next;
			}	
		}
	}
	
	public void phaseTH(int taskNum, int procNum, float[][] vertexWeight, float[][] edgeWeight){
		float aest;
		updateFixedCopy(taskNum, procNum);
		updateAllProcPerTask(taskNum,procNum);
		deleteAdan(procNum, taskNum);
		boolean[] isNoParent=new boolean[taskNum];
		for(int i=0; i<taskNum; i++){//判断任务是否有孩子
			isNoParent[i]=true;
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[j][i]>0)
					isNoParent[i]=false;
			}
		}
		float[][] est=new float[taskNum][procNum];		
		
		TaskNode currNode=priorBLevel.first;
		while(currNode!=null){
			updateIdleList(procNum);
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			if(allProcPerTask[taskSN].count>0){
				ScheduleNode tempNode=allProcPerTask[taskSN].first;//获得当前任务的第一个处理器情况结点
				while(tempNode!=null){
					ScheduleElement tempElement=(ScheduleElement)tempNode.info;
					int procSN=tempElement.processorID;
					ScheduleElement changeNode=tempElement.getCopy();
					est[taskSN][procSN]=calcEST(taskSN, procSN, taskNum, procNum, est, isNoParent, edgeWeight, vertexWeight);
					aest=calcAST(taskSN, procSN, tempElement.startTime, est[taskSN][procSN], idleLists[procSN], vertexWeight);
					allProcPerTask[taskSN].updateNode(changeNode, aest, aest+vertexWeight[taskSN][procSN]);//update 
					origResultsPerProc[procSN].updateNode(changeNode, aest, aest+vertexWeight[taskSN][procSN]);
					tempNode=tempNode.next;
				}
			}
			currNode=currNode.next;
		}
		updateFixedCopy(taskNum, procNum);
	}
	
	public void phaseND(int taskNum, int procNum, float[][] vertexWeight, float[][] edgeWeight){
		float aest;
		updateFixedCopy(taskNum, procNum);
		deleteAdan(procNum, taskNum);
		
		/*for(int i=0; i<taskNum; i++){
			System.out.println("Task "+i+":"+procFixedCopy[i]);	
		}*/
		
		boolean[] isNoParent=new boolean[taskNum];
		for(int i=0; i<taskNum; i++){//判断任务是否有孩子
			isNoParent[i]=true;
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[j][i]>0)
					isNoParent[i]=false;
			}
		}
		float[][] est=new float[taskNum][procNum];		
		
		TaskNode currNode=priorBLevel.first;
		while(currNode!=null){
			updateIdleList(procNum);
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			if(allProcPerTask[taskSN].count>1){
				ScheduleNode tempNode=allProcPerTask[taskSN].first;//获得当前任务的第一个处理器情况结点
				while(tempNode!=null){
					ScheduleElement tempElement=(ScheduleElement)tempNode.info;
					int procSN=tempElement.processorID;
					ScheduleElement changeNode=tempElement.getCopy();
					est[taskSN][procSN]=calcEST(taskSN, procSN, taskNum, procNum, est, isNoParent, edgeWeight, vertexWeight);
					aest=calcAST(taskSN, procSN, tempElement.startTime, est[taskSN][procSN], idleLists[procSN], vertexWeight);
					allProcPerTask[taskSN].updateNode(changeNode, aest, aest+vertexWeight[taskSN][procSN]);//update 
					origResultsPerProc[procSN].updateNode(changeNode, aest, aest+vertexWeight[taskSN][procSN]);
					tempNode=tempNode.next;
				}
			}
			currNode=currNode.next;
		}
		updateFixedCopy(taskNum, procNum);
		
		/*for(int i=0; i<taskNum; i++){
			System.out.println("Task "+i+":"+procFixedCopy[i]);	
		}*/
	}
	
	public void updateFixedCopy(int taskNum, int procNum){
		for(int i=0; i<taskNum; i++)
			procFixedCopy[i]=new ScheduleElement(0, 0, Float.MAX_VALUE, Float.MAX_VALUE);
		float[] minFT=new float[taskNum];		
		TaskNode currNode=new TaskNode();
		currNode=prior.first;//按优先级队列取任务
		while(currNode!=null){
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			
			minFT[taskSN]=Float.MAX_VALUE;
			for(int i=0;i<procNum;i++){
				if(origResultsPerProc[i].isfindTask(taskSN)==true){
					ScheduleElement sElement=origResultsPerProc[i].findTask(taskSN);
					if(sElement.endTime<minFT[taskSN]){
						minFT[taskSN]=sElement.endTime;
						procFixedCopy[taskSN].setNum(taskSN, sElement.processorID, sElement.startTime, sElement.endTime);
					}
				}
			}//搜索一次schedule，为currTask找fixed copy and all processors
			currNode=currNode.next;
		}//搜索所有的tasks
	}
	
	public float calcEST(int taskSN, int procSN, int taskNum, int procNum, float[][] est, boolean[] isNoParent, float[][] edgeWeight, float[][] vertexWeight){		
		updateFixedCopy(taskNum, procNum);
		deleteAdan(procNum, taskNum);
		float aest;	
		if(isNoParent[taskSN]==true){
			est[taskSN][procSN]=0;
		}else{
			for(int j=0; j<taskNum; j++){
				if(edgeWeight[j][taskSN]!=0){//is a parent of task
					//calculate the earliest start time of all copies of parents and shift tasks
					ScheduleNode currCopyOfParent=allProcPerTask[j].first;//the first copy of parent node
					ScheduleElement currCopyOfChildElement=currCopyOfParent.info;
					int currChildProc=currCopyOfChildElement.processorID;
					while(currCopyOfParent!=null){
						if(isNoParent[j]==true){
							est[j][currChildProc]=0;
						}else{
							//calculate est of parent;
							updateFixedCopy(taskNum, procNum);
							est[j][currChildProc]=0;
							for(int k=0; k<taskNum; k++){//each task
								if(edgeWeight[k][j]>0){//is parent
									ScheduleElement recordElement=origResultsPerProc[currChildProc].findTask(k);
									if(origResultsPerProc[currChildProc].isfindTask(k)==true && recordElement.endTime<=currCopyOfChildElement.startTime){ //find a copy in the same processor
										est[j][currChildProc]=Math.max(est[j][currChildProc], recordElement.endTime);
									}else{//find the fixed copy
										est[j][currChildProc]=Math.max(est[j][currChildProc], procFixedCopy[k].endTime+edgeWeight[k][j]);//前提更新procFixedCopy
									}
								}
							}
						}
						//计算est[j][currChildProc]完毕，下面接着计算任务实际可移动的时间AST
						ScheduleElement changeNode=currCopyOfChildElement.getCopy();
						aest=calcAST(j, currChildProc, currCopyOfChildElement.startTime, est[j][currChildProc], idleLists[currChildProc], vertexWeight);
						allProcPerTask[j].updateNode(changeNode, aest, aest+vertexWeight[j][currChildProc]);//update 
						origResultsPerProc[currChildProc].updateNode(changeNode, aest, aest+vertexWeight[j][currChildProc]);
						currCopyOfParent=currCopyOfParent.next;
					}					
				}
			}
			//计算当前任务的EST及AST
			updateFixedCopy(taskNum, procNum);
			
			for(int j=0; j<taskNum; j++){//each task
				if(edgeWeight[j][taskSN]>0){//is parent
					ScheduleElement recordElement=origResultsPerProc[procSN].findTask(j);
					if(origResultsPerProc[procSN].isfindTask(j)==true && recordElement.endTime<=origResultsPerProc[procSN].findTask(taskSN).startTime){ //find a copy in the same processor
						est[taskSN][procSN]=Math.max(est[taskSN][procSN], recordElement.endTime);
					}else{//find the fixed copy
						est[taskSN][procSN]=Math.max(est[taskSN][procSN], procFixedCopy[j].endTime+edgeWeight[j][taskSN]);//前提更新procFixedCopy
					}
				}
			}
		}
		return est[taskSN][procSN];
	}
	
	public float calcAST(int taskSN, int procSN, float st, float estcurr, IdleList idleLists, float[][] vertexWeight){
		float aest;	
		idleLists.insertNode(new PairElement(st, st+vertexWeight[taskSN][procSN]));//将原有的执行删除
		PairElement findElement=new PairElement(Float.MAX_VALUE,Float.MAX_VALUE);//找到一个满足条件的最大的空闲块
		LinkedListNode currNode=idleLists.first;
		while(currNode!=null){
			PairElement pElement=(PairElement)currNode.info;
			if(pElement.start<findElement.start)
				if(st>=pElement.start)
					if(pElement.end>=Math.max(estcurr, pElement.start)+vertexWeight[taskSN][procSN]){		
						findElement.setNum(pElement.start, pElement.end);
					}
			currNode=currNode.next;
		}
		aest=Math.max(estcurr, findElement.start);
		idleLists.updataIdleNode(findElement,aest,aest+vertexWeight[taskSN][procSN]);
		return aest;
	}
	
	public float calcLFT(int taskSN, int procSN, int taskNum, int procNum, ScheduleElement[] procFixedCopy, float[][] edgeWeight, float[][] lft){
		ScheduleElement deleteElement=origResultsPerProc[procSN].deleteNode(taskSN);
		allProcPerTask[taskSN].deleteNode(deleteElement);
		
		updateFixedCopy(taskNum, procNum);
	
		deleteAdan(procNum, taskNum);
		
		ScheduleNode firstSche=new ScheduleNode();
		ScheduleElement firstElement=new ScheduleElement();
		if(procFixedCopy[taskSN].startTime==procFixedCopy[taskSN].endTime){//无Fixed copy
			for(int i=0; i<procNum; i++){
				firstSche=origResultsPerProc[i].first;
				if(i==procSN){//同处理器上的任务
					while(firstSche!=null){
						firstElement=(ScheduleElement)firstSche.info;
						if(edgeWeight[taskSN][firstElement.taskID]>0){
							//three conditions:孩子结点；同处理器；在当前任务之后
							if(lft[taskSN][procSN]>firstElement.startTime){
								lft[taskSN][procSN]=Math.min(lft[taskSN][procSN],firstElement.startTime);
							}
						}
						firstSche=firstSche.next;
					}
				}else{
					while(firstSche!=null){
						firstElement=(ScheduleElement)firstSche.info;
						if(edgeWeight[taskSN][firstElement.taskID]>0){
							//three conditions:孩子结点；同处理器；在当前任务之后
							if(lft[taskSN][procSN]>firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]){
								lft[taskSN][procSN]=Math.min(lft[taskSN][procSN],firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]);
							}
						}
						firstSche=firstSche.next;
					}
				}	
			}
		}else{//Fixed copy不为空
			for(int i=0; i<procNum; i++){
				firstSche=origResultsPerProc[i].first;
				if(i==procSN){//同处理器上的任务
					while(firstSche!=null){
						firstElement=(ScheduleElement)firstSche.info;
						if(edgeWeight[taskSN][firstElement.taskID]>0){
							//three conditions:孩子结点；同处理器；在当前任务之后
							if(firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]<procFixedCopy[taskSN].endTime){
								lft[taskSN][procSN]=Math.min(lft[taskSN][procSN],firstElement.startTime);//若fixed copy不能提供数据，则由该任务提供
							}
						}
						firstSche=firstSche.next;
					}
				}else{
					ScheduleElement localParent=origResultsPerProc[i].findTask(taskSN);
					while(firstSche!=null){//首先判断是否有本地父节点
						firstElement=(ScheduleElement)firstSche.info;
						if(edgeWeight[taskSN][firstElement.taskID]>0){
							//three conditions:孩子结点；同处理器；在当前任务之后
							if(localParent==null){
								if(firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]<procFixedCopy[taskSN].endTime){
									lft[taskSN][procSN]=Math.min(lft[taskSN][procSN],firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]);//若fixed copy不能提供数据，则由该任务提供
								}
							}else{
								if(firstElement.startTime<localParent.endTime){
									if(firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]<procFixedCopy[taskSN].endTime){
										lft[taskSN][procSN]=Math.min(lft[taskSN][procSN],firstElement.startTime-edgeWeight[taskSN][firstElement.taskID]);//若fixed copy不能提供数据，则由该任务提供
									}
								}
							}
						}
						firstSche=firstSche.next;
					}
				}	
			}
		}
		
		origResultsPerProc[procSN].insertNode(deleteElement);
		allProcPerTask[taskSN].insertNode(deleteElement);
		
		updateFixedCopy(taskNum, procNum);
	
		deleteAdan(procNum, taskNum);
		
		return lft[taskSN][procSN];
	}
	
	public float calcAFT(int taskSN, int procSN, float ft, float lftcurr, IdleList idleLists, float[][] vertexWeight){
		float alft;	
		idleLists.insertNode(new PairElement(ft-vertexWeight[taskSN][procSN],ft));//将原有的执行删除
		PairElement findElement=new PairElement();//找到一个满足条件的最大的空闲块
		LinkedListNode currNode=idleLists.first;
		while(currNode!=null){
			PairElement pElement=(PairElement)currNode.info;
			if(ft<=pElement.end)
				if(pElement.start<=Math.min(lftcurr, pElement.end)-vertexWeight[taskSN][procSN]){
					if(pElement.end>findElement.end){
						findElement.setNum(pElement.start, pElement.end);
					}
				}
			currNode=currNode.next;
		}
		alft=Math.min(lftcurr, findElement.end);
		idleLists.updataIdleNode(findElement,alft-vertexWeight[taskSN][procSN],alft);
		return alft;
	}	
	
	public void printSchedule(int procNum, int taskNum){
		System.out.println();
		for(int i=0; i<procNum; i++){
			System.out.println("Processor "+i+":");
			origResultsPerProc[i].print();
		}
	}
	
	public float timeCal(int procNum){
        float timeSum=0;	
        float totalTime=0;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        for(int i=0; i<procNum; i++){
        	ScheduleNode currentTask=origResultsPerProc[i].first;
    		while(currentTask!=null){
    			ScheduleElement perTask=currentTask.info;
    			if(flag[perTask.processorID]!=true)
    				flag[perTask.processorID]=true;
    			if(perTask.endTime>procTermTime[perTask.processorID])
    				procTermTime[perTask.processorID]=perTask.endTime;
    			timeSum+=(perTask.endTime-perTask.startTime);
    			currentTask=currentTask.next;
    		}
        }        
		
		for(int i=0; i<procNum; i++){
			//System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		return timeSum;
	}

	public int duplNums(int taskNum){
		int sum=0;
		for(int i=0; i<taskNum; i++){
			sum+=allProcPerTask[i].count;
		}
		return sum-taskNum;
	}
	
	public float makespan(int procNum){
		float curr=0;
		for(int i=0; i<procNum; i++){
			ScheduleNode currentTask=origResultsPerProc[i].first;
			while(currentTask!=null){
				if(curr<currentTask.info.endTime){
					curr=currentTask.info.endTime;
				}
				currentTask=currentTask.next;
			}
		}
		return curr;
	}
}

